package 栈队列与哈希表;


import java.util.ArrayList;

/**
 * 实现一个栈的数据结构，使其具有以下方法：
 * 压栈、弹栈、取栈顶元素、判断栈是否为空以及获取栈中元素个数
 */
public class A如何实现栈<T> {


    private ArrayList<T> arr;
    //数组中存储元素的个数
    private int stackSize;

    public A如何实现栈() {
        stackSize = 0;
        arr = new ArrayList<>();
    }

    boolean isEmpty() {
        return stackSize == 0;
    }

    //返回栈的大小
    int size() {
        return stackSize;
    }

    //返回栈顶元素
    T top() {
        if (isEmpty()) {
            return null;
        }
        return arr.get(stackSize - 1);
    }

    //弹栈
    T pop() {
        if (stackSize > 0) {
            return arr.get(--stackSize);
        } else {
            System.out.println("栈已经为空");
            return null;
        }
    }

    //压栈
    void push(T item) {
        arr.add(item);
        stackSize++;
    }
}

class Test {
    public static void main(String[] args) {
        A如何实现栈 a如何实现栈 = new A如何实现栈<Integer>();
        a如何实现栈.push(1);

        System.out.println("栈顶元素为：" + a如何实现栈.top());
        System.out.println("栈大小为：" + a如何实现栈.size());
        a如何实现栈.pop();
        System.out.println("弹栈成功");
        a如何实现栈.pop();
    }
}

/**
 * 链表实现栈
 *
 * @param <T>
 */
class LNode<T> {
    T data;
    LNode<T> next;
}

class AB用链表实现栈<T> {

    private LNode<T> pHead;

    public AB用链表实现栈() {
        pHead = new LNode<T>();
        pHead.data = null;
        pHead.next = null;
    }

    //判断stack是否为空，如果为空返回true，否则返回false
    boolean empth() {
        return pHead == null;
    }

    //获取栈中元素的个数
    int size() {
        int size = 0;
        LNode<T> p = pHead.next;
        while (p != null) {
            p = p.next;
            size++;
        }
        return size;
    }

    //入栈，把c放到栈顶
    void push(T c) {
        LNode<T> p = new LNode<T>();
        p.data = c;
        p.next = pHead.next;
        pHead.next = p;
    }

    //出栈，同时返回栈顶元素
    T pop() {
        LNode<T> tmp = pHead.next;
        if (tmp != null) {
            pHead.next = tmp.next;
            return tmp.data;
        }
        System.out.println("栈已经为空");
        return null;
    }

    //取得栈顶元素
    T top() {
        if (pHead.next != null) {
            return pHead.next.data;
        }
        System.out.println("栈已经为空");
        return null;
    }
}

class Test1 {
    public static void main(String[] args) {
        AB用链表实现栈<Integer> ab用链表实现栈 = new AB用链表实现栈<>();

        ab用链表实现栈.push(1);
        System.out.println("栈顶元素为：" + ab用链表实现栈.top());
        System.out.println("栈大小为：" + ab用链表实现栈.size());
        ab用链表实现栈.pop();
        System.out.println("弹栈成功");
        ab用链表实现栈.pop();
    }
}